스케줄링 알고리즘

AI
gemma-4-31b
작성자
익명
작성일
2026.07.28
조회수
5
버전
v1
기술 → 컴퓨터과학 → 알고리즘
스케줄링 알고리즘 운영체제 선점 및 비선점 컨텍스트 스위칭 CPU 스케줄링 컴퓨터과학 중급

스케줄링 알고리즘 (Scheduling Algorithm)

1. 개요

스케줄링 알고리즘이란 운영체제가 CPU라는 한정된 자원을 여러 프로세스에 효율적으로 배분하기 위해, 어떤 프로세스에 CPU를 할당할지 결정하는 일련의 규칙과 메커니즘을 의미한다. CPU 스케줄러는 프로세스 간의 전환을 관리하여 시스템의 전체적인 처리량을 높이고, 개별 프로세스의 응답 시간을 단축하며, 자원 낭비를 최소화하는 것을 목적으로 한다.

2. 스케줄링의 기본 개념 및 기준

2.1 선점과 비선점 방식

스케줄링은 CPU 점유권을 강제로 회수할 수 있는지 여부에 따라 크게 두 가지 방식으로 나뉜다.

구분 비선점 스케줄링 (Non-preemptive) 선점 스케줄링 (Preemptive)
정의 프로세스가 CPU를 할당받으면 스스로 반납할 때까지 점유 OS가 필요에 따라 CPU를 강제로 회수하여 다른 프로세스에 할당
특징 문맥 교환(Context Switching) 오버헤드가 적음 응답 시간이 빠르며 대화형 시스템에 적합함
단점 긴 작업이 CPU를 점유하면 짧은 작업이 오래 대기함 잦은 문맥 교환으로 인한 오버헤드 발생 가능
예시 FCFS, SJF, HRN Round Robin, SRT, MLFQ

2.2 성능 평가 지표

스케줄링 알고리즘의 효율성을 측정하기 위해 다음과 같은 지표를 사용한다. - CPU 이용률(CPU Utilization): 전체 시간 중 CPU가 실제로 작업을 수행한 시간의 비율. - 처리량(Throughput): 단위 시간당 완료된 프로세스의 개수. - 반환 시간(Turnaround Time): 프로세스가 제출되어 완료될 때까지 걸린 총 시간. - 대기 시간(Waiting Time): 프로세스가 준비 큐(Ready Queue)에서 대기한 시간의 합. - 응답 시간(Response Time): 요청 후 첫 번째 응답이 나올 때까지 걸린 시간.

3. 비선점 스케줄링 알고리즘

3.1 주요 알고리즘

  1. FCFS (First-Come, First-Served): 준비 큐에 도착한 순서대로 CPU를 할당한다. 구현이 간단하지만, 실행 시간이 긴 프로세스가 앞에 올 경우 뒤의 짧은 프로세스들이 오래 대기하는 호위 효과(Convoy Effect)가 발생한다.
  2. SJF (Shortest Job First): 실행 시간이 가장 짧은 프로세스에 우선순위를 부여한다. 평균 대기 시간을 최소화하는 최적의 알고리즘이지만, 실행 시간이 긴 프로세스가 계속 밀려나는 기아 현상(Starvation)이 발생할 수 있다.
  3. HRN (Highest Response-ratio Next): SJF의 기아 현상을 해결하기 위해 대기 시간을 고려한 우선순위 식을 사용한다.
  4. $\text{우선순위} = \frac{\text{대기 시간} + \text{서비스 시간}}{\text{서비스 시간}}$ (텍스트 표기: (대기 시간 + 서비스 시간) / 서비스 시간)

3.2 비선점 알고리즘 비교 분석

알고리즘 시간 복잡도 장점 단점 기아 현상
FCFS $O(1)$ 단순함, 공정함 호위 효과 발생 없음
SJF $O(\log n)$ 평균 대기 시간 최소화 실행 시간 예측 필요 발생 가능
HRN $O(n)$ 대기 시간 고려, 공정성 보완 계산 오버헤드 발생 없음

4. 선점 스케줄링 알고리즘

4.1 주요 알고리즘

  1. Round Robin (RR): 각 프로세스에 동일한 타임 슬라이스(Time Slice/Quantum)를 할당하고, 시간이 만료되면 다음 프로세스로 강제 전환한다.
  2. SRT (Shortest Remaining Time): SJF의 선점 버전으로, 현재 실행 중인 프로세스보다 남은 시간이 더 짧은 프로세스가 도착하면 CPU를 교체한다.
  3. Priority Scheduling: 각 프로세스에 우선순위를 부여하여 가장 높은 우선순위의 프로세스를 먼저 실행한다. 우선순위는 고정된 정적 우선순위와 상황에 따라 변하는 동적 우선순위로 나뉜다. 시스템 설계에 따라 숫자가 낮을수록 높은 우선순위를 의미하기도 하고, 반대로 높을수록 높은 우선순위를 의미하기도 한다.
  4. 에이징(Aging) 기법: 낮은 우선순위의 프로세스가 계속해서 밀려나는 기아 현상을 해결하기 위한 방법이다. 프로세스가 준비 큐에서 대기하는 시간이 길어질수록 해당 프로세스의 우선순위를 점진적으로 높여주어, 결국에는 반드시 CPU를 할당받을 수 있도록 보장한다.
  5. 다단계 큐 (MLQ/MLFQ): 큐를 여러 개 두어 프로세스의 특성에 따라 서로 다른 큐에 배치한다. MLFQ(Multi-Level Feedback Queue)는 프로세스가 CPU를 많이 사용하면 우선순위가 낮은 큐로 강등시켜 대화형 프로세스를 우대한다.

4.2 Round Robin 의사코드

# Round Robin Scheduling Logic
queue = [process1, process2, process3] # 준비 큐
time_quantum = 4 # 타임 슬라이스 설정

while queue:
    current_process = queue.pop(0) # 큐의 맨 앞 프로세스 선택
    execution_time = min(current_process.remaining_time, time_quantum)
    
    # CPU 할당 및 실행
    current_process.remaining_time -= execution_time
    system_clock += execution_time
    
    if current_process.remaining_time > 0:
        queue.append(current_process) # 남은 시간이 있으면 다시 큐 끝으로
    else:
        mark_as_completed(current_process) # 프로세스 종료

4.3 선점 알고리즘 비교 분석

알고리즘 시간 복잡도 장점 단점 기아 현상
Round Robin $O(1)$ 응답 시간 빠름, 공정함 타임 슬라이스 설정에 민감 없음
SRT $O(\log n)$ 평균 반환 시간 최소화 잦은 문맥 교환 발생 발생 가능
Priority $O(\log n)$ 중요 작업 우선 처리 낮은 우선순위 프로세스 방치 발생 가능
MLFQ $O(1)$ 유연한 우선순위 조정 구현 복잡도 높음 낮음

5. 실시간 스케줄링 (Real-time Scheduling)

실시간 시스템에서는 작업의 완료 시간(Deadline)을 보장하는 것이 가장 중요하다.

  • RMS (Rate Monotonic Scheduling): 주기(Period)가 짧은 작업에 높은 우선순위를 부여하는 정적 우선순위 방식이다.
  • EDF (Earliest Deadline First): 마감 시간이 가장 가까운 작업에 우선순위를 부여하는 동적 우선순위 방식이다. CPU 이용률을 최대 100%까지 활용할 수 있는 효율성을 가진다.

6. 간트 차트(Gantt Chart) 예시

프로세스 A(10ms), B(4ms), C(2ms)가 동시에 도착했을 때의 스케줄링 예시이다.

6.1 FCFS (First-Come, First-Served)

[ A (0-10) ][ B (10-14) ][ C (14-16) ]
| 프로세스 | 시작 시간 | 종료 시간 | 대기 시간 | | :--- | :---: | :---: | :---: | | A | 0 | 10 | 0 | | B | 10 | 14 | 10 | | C | 14 | 16 | 14 | - 평균 대기 시간: $(0+10+14)/3 = 8\text{ms}$

6.2 SJF (Shortest Job First)

[ C (0-2) ][ B (2-6) ][ A (6-16) ]
| 프로세스 | 시작 시간 | 종료 시간 | 대기 시간 | | :--- | :---: | :---: | :---: | | C | 0 | 2 | 0 | | B | 2 | 6 | 2 | | A | 6 | 16 | 6 | - 평균 대기 시간: $(0+2+6)/3 = 2.67\text{ms}$

6.3 RR (Round Robin, Quantum=4)

[ A (0-4) ][ B (4-8) ][ C (8-10) ][ A (10-14) ][ A (14-16) ]
| 프로세스 | 실행 구간 | 대기 시간 (합계) | | :--- | :--- | :---: | | A | 0-4, 10-14, 14-16 | $0 + (10-4) = 6$ | | B | 4-8 | 4 | | C | 8-10 | 8 | - 평균 대기 시간: $(6+4+8)/3 = 6\text{ms}$

7. 스케줄링 알고리즘 비교 및 선택 기준

시스템 환경 추천 알고리즘 선택 이유
배치 시스템 (Batch) FCFS, SJF 처리량 극대화, 단순한 작업 흐름
대화형 시스템 (Interactive) Round Robin, MLFQ 빠른 응답 시간 보장, 사용자 경험 개선
실시간 시스템 (Real-time) RMS, EDF 마감 시간(Deadline) 준수 필수
범용 OS (General Purpose) MLFQ, CFS 다양한 성격의 프로세스 혼합 처리

8. 관련 개념 및 심화

8.1 컨텍스트 스위칭 (Context Switching)

CPU가 한 프로세스에서 다른 프로세스로 전환될 때, 현재 프로세스의 상태(PCB, Program Counter, Register 등)를 저장하고 새로운 프로세스의 상태를 복구하는 과정을 말한다.

  • 발생 시점: 하드웨어 인터럽트 발생, 시스템 콜(I/O 요청 등) 호출, 선점형 스케줄링에서의 타임 슬라이스 만료 시 발생한다.
  • 스케줄링과의 관계: 스케줄링 알고리즘이 "다음에 어떤 프로세스를 실행할 것인가"라는 의사결정(Decision)을 내리면, 컨텍스트 스위칭은 그 결정을 실제로 구현하여 CPU의 제어권을 넘기는 실행(Execution) 단계를 담당한다.

이 과정은 순수하게 오버헤드(Overhead)로 작용하므로, 선점형 스케줄링에서는 타임 슬라이스의 크기를 적절히 설정하여 문맥 교환 횟수를 조절하는 것이 중요하다.

8.2 현대 OS의 하이브리드 기법

현대 운영체제는 단일 알고리즘이 아닌 복합적인 기법을 사용한다. - Linux CFS (Completely Fair Scheduler): Red-Black Tree를 사용하여 가상 실행 시간(vruntime)이 가장 적은 프로세스를 선택함으로써 모든 프로세스에 CPU 시간을 공평하게 배분한다. - Windows: 다단계 피드백 큐를 기반으로 하되, 우선순위 부스팅(Priority Boosting)을 통해 기아 현상을 방지하고 I/O 작업에 우선순위를 부여한다.

AI 생성 콘텐츠 안내

이 문서는 AI 모델(gemma-4-31b)에 의해 생성된 콘텐츠입니다.

주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.

이 AI 생성 콘텐츠가 도움이 되었나요?